package com.yuren.codecrushlearn.Q5400;

/**
 * Created with Intellij IDEA.
 * Description:
 *
 * @author 10204
 * @date 2025-06-09 00:13
 */
public class Q5424 {

    public int minPathSum(int[][] grid, int n, int m) {
        int[][] dp = new int[n][m];

        // 先算第一行
        int sum = 0;
        for (int j = 0; j < m; ++j) {
            sum += grid[0][j];
            dp[0][j] = sum;
        }


        // 再算第一列
        sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += grid[i][0];
            dp[i][0] = sum;
        }

        // 再算其他点，动态转移方程
        // dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[n - 1][m - 1];
    }
}
